Access control lists (ACLs) are classification filters that enable network administrators to control the processing functions applied to incoming packets in packet-switched networks. As the processing functions are typically performed within a network switch, router or other appliance, the functions are generally offered as features of the appliance and thus referred to simply as “features.” ACLs were originally developed to enable administrators to specify packet forwarding rules (permitting packets meeting specified criteria to be forwarded, and denying others), but as the roles of network appliances have expanded to include various security features (e.g., encryption, TCP intercept, multicast flood suppression, VLAN-based, port-based and interface-based filters, ICMP packet suppression, etc.), quality-of-service features (e.g., rate limiting, traffic shaping, policy-based routing), billing features (e.g., accounting of traffic from a set of sources, or to a set of destinations) and so forth, so too has the demand for additional ACLs to specify whether to permit or deny application of such features to a given packet.
FIG. 1 illustrates a prior art packet processing system 100 that employs ACLs to make packet disposition decisions (e.g., permit or deny application of a given feature to an incoming packet). As shown, a stream of packets 101 is supplied to a packet processor 102 such as a network processing unit (NPU) or central processing unit (CPU). The packet processor 102 constructs a search key 104 from selected fields within the packet header (e.g., source address, destination address, source port, destination port, protocol, etc.) and forwards the search key to a ternary content addressable memory 105 (TCAM). The TCAM is a specialized storage device that may be used to store binary representations of ACL rules (i.e., individual statements within an ACL that specify packet header field values, including wildcards, that a user has associated with a given packet disposition) in respective TCAM entries, and that includes circuitry to compare the supplied search key 104 to all the TCAM entries in parallel, thus effecting effect an ACL search in which the matching TCAM entries or “hits” correspond to respective ACL rules that are satisfied by the packet being processed. In a typical TCAM architecture, multiple ACLs may be stored within respective array blocks or combinations of array blocks and searched in parallel. The TCAM of FIG. 1, for example, includes two array blocks 1081, 1082 to store a pair of ACLs (ACL1, ACL2), with each array block 108 including a TCAM array 110 to store the ACL rules in respective entries (i.e., rules of ACL1 in array block 1081 and rules of ACL2 in array block 1082), and a priority encoder 112 to receive search results (i.e., via match lines 114) during each search operation and to generate a hit index (also referred to as a match address) that indicates the TCAM entry that yielded the highest priority match, and also a hit signal that indicates whether at least one match was detected. When multiple hits occur, the highest priority match is typically resolved by physical location of the matching entries, for example, with the entry in the lowest numbered row of the TCAM array being selected as the highest priority match. Thus, in a search operation within the TCAM of FIG. 1, each of the array blocks yields a hit signal (“Hit1” and “Hit2”) and corresponding hit index (“Indx1” and “Indx2”) for a respective one of the two ACLs (ACL1 and ACL2), each hit signal/hit index pair constituting a TCAM search result 115 (SSslt1 and SRslt2) that is returned to the packet processor 102. Typically, there are multiple array blocks (e.g., 16/32/64 are common numbers of array blocks) in a modem TCAM, and a block-level priority encoder is provided to select the highest matching location from among the match information from all the blocks. When two search results are to be output from the TCAM in parallel, search results from half of the array blocks are encoded by one block priority encoder to produce the first output search result, and search results from the other half of the array blocks are encoded by the another block priority encoder to produce the second output search result.
The packet processor 102 applies the TCAM search results 115 to address (i.e., index) an action lookup table stored within a static random access memory 120 (SRAM), and thus retrieve an action value 117 that indicates an action to be taken with respect to the packet (e.g., permit or deny application of the feature to which the ACL pertains) and a possible set of ancillary actions (e.g., count occurrence of the ACL-rule match, log an error or other value, save the packet to disk or other storage for later inspection, etc.). When all the action values 117 relating to a given packet have been retrieved, the packet processor 102 may combine the actions according to a programmed algorithm to yield a final packet action and final set of ancillary actions which are applied to permit or deny delivery of the packet to the pertinent feature and carry out the indicated ancillary actions.
Although suitable for relatively simple applications, packet processing system 100 does not scale well as the number of ACLs increases which, unfortunately, is exactly the trend as both the number of features and the number of ACLs per feature continue to escalate rapidly. In particular, TCAMs in the present state of the art are typically I/O (input/output) constrained and capable of outputting only a small number of search results in parallel. For example, more modern TCAM devices are capable of outputting two search results per search cycle, with next generation devices projected to output four search results per cycle. Accordingly, TCAMs are generally used to store and search only a small number of ACLs per packet and thus place a ceiling on the number of supported ACLs. Unfortunately, system cost and complexity increases quickly if more TCAMs are added to meet the demand for additional ACL storage, and performance penalties result if the number of ACLs required to be searched per TCAM exceed the TCAM output capability.
One approach for increasing ACL processing bandwidth is to pre-process ACLs when first defined and merge ACLs (in software, typically in the control plane) where possible prior to their storage within the TCAM. Unfortunately, pre-merging of ACLs tends to produce a resultant ACL that is equivalent to the cross-product of the merged ACLs and thus consumes exponentially more storage within the TCAM. Making matters worse, it is usually difficult to predict the efficiency of the pre-merge operation and thus whether a pre-merge of two or more ACLs will exceed the storage capacity of the TCAM. This leaves system designers in the unfortunate position of learning at time of network configuration whether the network appliance being configured is unable to support a desired combination of features.